# -*- coding: utf-8 -*-
# @Time    : 2019/3/5 17:41
# @Author  : z.t.b
# @Email   : zhtbin@163.com
# @File    : findRewardCombination.py
# @Software: PyCharm
"""
奖赏组合方式
有1、2、5、10面额的硬币，在限定总额的情况下，求所有可能的加和方式
if total reward is 5 expect
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[5]

"""


class Solution(object):

    rewards = (1, 2, 5, 10)

    # totalReward奖赏总额
    # 结果集合
    def find(self, total_reward, result=[]):
        if total_reward == 0:
            print(result)
            return
        elif total_reward < 0:
            return
        else:
            for reward in self.rewards:
                new_result = result[:]
                new_result.append(reward)
                self.find(total_reward - reward, new_result)


if __name__ == "__main__":
    solution = Solution()
    solution.find(3, [])
